#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
/*
 * @lc app=leetcode.cn id=215 lang=cpp
 *
 * [215] 数组中的第K个最大元素
 */

// @lc code=start
class Solution {
public:

    // int findKthLargest(vector<int>& nums, int k) {
    //     //  6 5 3 2 1
    //     priority_queue<int, vector<int>, greater<int>> q;
    //     for (int i = 0; i < nums.size(); i++) {
    //         if (q.size() < k) q.push(nums[i]);
    //         else if (nums[i] >= q.top()) {
    //             q.pop(); q.push(nums[i]);
    //         }
    //     }
    //     return q.top();
    // }

    // O(n), 利用快排的思想, 如果最后的位置在n - k的位置, 就是正确答案
    int findKthLargest(vector<int>& nums, int k) {
        int index = nums.size() - k, sz = nums.size();
        int l = 0, r = sz; // [ )
        while (true) {
            int pivot = rand() % (r - l) + l;
            swap(nums[pivot], nums[l]);
            int least = l, cur = l + 1;
            while (cur < r) {
                if (nums[cur] <= nums[l]) {
                    least++; swap(nums[least], nums[cur]);
                }
                cur++;
            }
            swap(nums[l], nums[least]);
            if (least == index) return nums[least];
            else if (least < index) l = least + 1;
            else r = least;
        }
        return 0;
        
    }
};
// @lc code=end

